#include "TestGraphAlgorithms.h"
#include "Graph.h"
#include "MakeGraph.h"
#include "GraphAlgorithms.h"
#include <set>
#include <vector>
const int NUMBER_OF_TESTS = 30;
const int MAX = INT_MAX/10000000;

inline bool IfPathExists(Graph &graph, int from, int to, std::vector<bool> &visited) {
    if(visited[from]) return false;
    visited[from] = true;
    if(from == to) return true;
    std::set<int> incidence_list = graph.GetIncidentList(from);
    for(std::set<int>::iterator vertex = incidence_list.begin(); vertex != incidence_list.end(); vertex++){
        if(IfPathExists(graph, *vertex, to, visited)) return true;
    }
    return false;
}

inline bool IfPathExists(Graph &graph, int from, int to){
    std::vector<bool> visited(graph.GetNumberOfVertices());
    return IfPathExists(graph, from, to, visited);
}

std::set<std::set<int> > StupidTarjan(Graph &graph){
    std::set< std::set<int> > answer;
    std::vector<bool> if_added_to_component(graph.GetNumberOfVertices(), false);
    for (int vertex = 0; vertex < graph.GetNumberOfVertices(); vertex++) {
	if (if_added_to_component[vertex]) continue;
	if_added_to_component[vertex] = true;
	std::set<int> new_component;
	new_component.insert(vertex);
	for (int current_vertex = 0; current_vertex < graph.GetNumberOfVertices(); current_vertex++) {
	    if (if_added_to_component[current_vertex]) continue;
	    if (IfPathExists(graph, vertex, current_vertex) && IfPathExists(graph,current_vertex, vertex)) {
		new_component.insert(current_vertex);
		if_added_to_component[current_vertex] = true;
	    }
	}
	answer.insert(new_component);
    }
    return answer;
}

void TestTarjan(int vertices_number, std::vector<edge> edges){
    std::auto_ptr<Graph> graph = MakeCompactGraph(vertices_number, edges);
    TarjanAlgo tarjan(vertices_number);
    DepthFirstSearch(*graph, tarjan);
    std::vector<std::set<int> > answer = tarjan.GetComponents();
    std::set<std::set <int > > set_answer (answer.begin(), answer.end());
    std::set<std::set <int > > right_answer = StupidTarjan(*graph);
    if(right_answer != set_answer){
        throw std::logic_error("TarjanAlgo ERROR : wrong answer");
    }
}


void TestTarjan(){
    for(int test = 0; test < NUMBER_OF_TESTS; test++){
        int vertices_number = rand() % MAX + 1;
        std::vector<edge> edges = MakeRandomEdges(vertices_number);
        TestTarjan(vertices_number, edges);
    }
}



void GenerateAllGraphs(int vertices_number, int step, std::vector<edge> &edges){
    if(step == vertices_number * vertices_number){
        TestTarjan(vertices_number, edges);
    }
    else{
        GenerateAllGraphs(vertices_number, step+ 1, edges);
        edge new_edge(step / vertices_number, step % vertices_number);
        GenerateAllGraphs(vertices_number, step + 1, edges);
    }
}

void TestTarjanOnSmallGraphs(){
    std::vector<edge> edges;
    GenerateAllGraphs(1, 0, edges);
    edges.clear();
    GenerateAllGraphs(2, 0, edges);
    edges.clear();
    GenerateAllGraphs(3, 0, edges);
    edges.clear();
    GenerateAllGraphs(4, 0, edges);
}

void TestTarjanShuffle(){
    for(int test = 0; test < NUMBER_OF_TESTS; test++){
        int vertices_number = rand() % MAX + 1;
        std::vector<edge> edges = MakeRandomEdges(vertices_number);
        std::auto_ptr<Graph> graph = MakeCompactGraph(vertices_number, edges);
        TarjanAlgo tarjan_before(vertices_number);
        DepthFirstSearch(*graph, tarjan_before);
        int result_before_shuffle = tarjan_before.GetComponents().size();
        std::vector<int> shuffle(vertices_number);
        for(int vertex = 0; vertex < shuffle.size(); vertex++){
            shuffle[vertex] = vertex;
        }
        std::random_shuffle(shuffle.begin(), shuffle.end());
        for(int current_edge = 0; current_edge < edges.size(); current_edge++){
            int from = shuffle[edges[current_edge].from];
            int to = shuffle[edges[current_edge].to];
            edges[current_edge].from = from;
            edges[current_edge].to = to;
        }
        TarjanAlgo tarjan_after(vertices_number);
        DepthFirstSearch(*graph, tarjan_after);
        int result_after_shuffle = tarjan_after.GetComponents().size();
        if(result_after_shuffle != result_before_shuffle){
            throw std::logic_error("Tarjan Algorithm ERROR : wrong answer");
        }
    }
}



void TestAllAlgorithms(){
    TestTarjan();
    TestTarjanOnSmallGraphs();
    TestTarjanShuffle();
}